package com.mamingchao.basic.swardToOffer.three;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 解决问题思路：
 * 看过数学之美里面，关于搜索引擎 地图上搜索最优路线的算法
 * 使用图 + 迭代的方法，想到此问题也同理
 * 地图导航搜索最优路径，从起点a到t，中间可以切割a到b最优计算，b到c最优路径计算，..... 最终是s到t的最优路径计算
 * 其中切割分离出来的每个局部，都应该是最优的。比如 b到c如果有更优路线，那b到c应该换成 更优路线，a到t才能最优
 *
 * 所以，上面的理论，复用到小红杀怪这个上面，也不合适；因为上面的例子里，b c d等中间节点都是固定的，而此题不固定，a b x y的值不一样，节点就不一样
 *
 * 上网查里 有权图的最短路径算法；固定起点的 有Dijkstra（迪科斯彻）最短路算法；算所有节点之间的最短路径，用FLoyd（佛洛依德）算法
 * 但是这两种算法都是先用二维数据表示出图（邻接矩阵）来；当为稀疏表（边n的数量远小于节点m 的平方），用邻接表替代邻接矩阵，节省空间
 *
 * 如果想用图来实现，必须先把图算出来（画出来），然后再用二维数组表达，再套用上面的两个算法。这样做有点过于繁琐
 *
 *
 * 简单实现；用迭代，迭代里面的逻辑 有简单的判断；把a 和b 的血量加在一起当血量池
 *
 * 起点：满血的怪物a和b； 终点，怪物a和b 的血量都<=0
 *
 * 做测试，暴力递归是最差的，当  int wizard_x = 10;   int wizard_y = 5; 血量
 *
 */
public class XiaoHongKillMonster {

    public static void main(String[] args) {
        int blood_a = 86;
        int blood_b = 91;
        int wizard_x = 10;
        int wizard_y = 5;
        long start1 = System.currentTimeMillis();
        int result = getUsedWizardTimes(blood_a, blood_b, wizard_x, wizard_y);
        long end1 = System.currentTimeMillis();

        System.out.println("小红击杀怪物，一共用了 " + result + " 次！所用时间-- " + (end1 - start1));
        System.out.println("-----------------------------------------------");

        long start2 = System.currentTimeMillis();
        int result1 = getUsedWizardTimesWithRecursion(blood_a,blood_b,wizard_x,wizard_y,0);
        long end2 = System.currentTimeMillis();
        System.out.println("小红击杀怪物，一共用了 " + result1 + " 次！ 所用时间-- " + (end2 - start2) );

        System.out.println("-----------------------------------------------");
        HashMap<String, Integer> dp = new HashMap();
//        int reslut2 = getUsedWizardTimesWithDP(blood_a,blood_b,wizard_x,wizard_y,0,dp);
        long start3 = System.currentTimeMillis();
        int reslut2 = getUsedWizardTimesWithDP(blood_a,blood_b,wizard_x,wizard_y);
        long end3 = System.currentTimeMillis();
        System.out.println("小红击杀怪物，一共用了 " + reslut2 + " 次！ 所用时间-- " + (end3 - start3));
    }


    /**
     * 使用递归的方案实现；
     * @param blood_a_ 怪物A的血量
     * @param blood_b_ 怪物B的血量
     * @param wizard_x 小红单体技能x的血量伤害
     * @param wizard_y 小红群体技能y的血量伤害
     * @return 使用最少法术击杀a 和b 怪物的次数
     */
    private static int getUsedWizardTimesWithRecursion(double blood_a_,double blood_b_,  double wizard_x, double wizard_y, Integer wizard_num) {

        // base case
        // 如果a 和 b 血量都小于等于0，怪物就完成击杀
        if (blood_a_ <= 0 && blood_b_ <= 0) {
            return wizard_num;
        } else if(blood_a_ <= 0 ){
            // 使用一次x技能击杀b
            double temp = blood_b_/Math.max(wizard_x, wizard_y);
            return (int) (wizard_num + Math.ceil(temp));
        } else if(blood_b_ <= 0){
            // 使用一次x技能击杀a
            double temp = blood_a_/Math.max(wizard_x, wizard_y);
            return (int) (wizard_num + Math.ceil(temp));
        } else if (blood_a_ <= wizard_y && blood_b_ <= wizard_y) {
            return ++ wizard_num ;
        }


        // 当次选择1: 对a怪物使用一次x技能
        int choice1 =  getUsedWizardTimesWithRecursion(blood_a_ - wizard_x, blood_b_, wizard_x, wizard_y,  wizard_num + 1);
        // 当次选择2: 对b物使用一次x技能
        int choice2 =  getUsedWizardTimesWithRecursion(blood_a_ , blood_b_- wizard_x, wizard_x, wizard_y, wizard_num + 1);
        // 当次选择3: 对a和b怪物使用一次y技能
        int choice3 =  getUsedWizardTimesWithRecursion(blood_a_ - wizard_y, blood_b_- wizard_y, wizard_x, wizard_y,  wizard_num + 1);

        return getMinimunNum(getMinimunNum(choice1,choice2), choice3);

    }
    /**
     * 这个是自己实现的，有问题；没有做到从0~怪物血量的逐渐填满
     * 使用动态规划的方案实现；因为下面的贪心算法，我觉得可能不太准；不过方法封装，写的很漂亮
     * @param blood_a_ 怪物A的血量
     * @param blood_b_ 怪物B的血量
     * @param wizard_x 小红单体技能x的血量伤害
     * @param wizard_y 小红群体技能y的血量伤害
     * @return
     */
    private static int getUsedWizardTimesWithDP(int blood_a_, int blood_b_, int wizard_x, int wizard_y, Integer wizard_num, HashMap<String, Integer> dp) {
        // base case
        // 如果a 和 b 血量都小于等于0，怪物就完成击杀
        if (blood_a_ <= 0 && blood_b_ <= 0) {
           String key = upWizardNumOfCurKey(blood_a_,blood_b_,wizard_num,dp);
           return dp.get(key);
        } else if(blood_a_ <= 0 ){
            // 使用一次x技能击杀b
            double temp = blood_b_/Math.max(wizard_x, wizard_y);
            int newWizardNum =  (int) (wizard_num + Math.ceil(temp));
            String key = upWizardNumOfCurKey(blood_a_,blood_b_, newWizardNum, dp);
            return dp.get(key);
        } else if(blood_b_ <= 0){
            // 使用一次x技能击杀a
            double temp = blood_a_/Math.max(wizard_x, wizard_y);
            int newWizardNum =  (int) (wizard_num + Math.ceil(temp));

            String key = upWizardNumOfCurKey(blood_a_,blood_b_, newWizardNum, dp);
            return dp.get(key);
        } else if (blood_a_ <= wizard_y && blood_b_ <= wizard_y) {
            String key = upWizardNumOfCurKey(blood_a_,blood_b_, ++ wizard_num, dp);
            return dp.get(key);
        }


        // 当次选择1: 对a怪物使用一次x技能
        String key1 = upWizardNumOfCurKey(blood_a_ - wizard_x, blood_b_, wizard_num +1, dp);
        int choice1 = dp.get(key1);

        // 当次选择2: 对b物使用一次x技能
        String key2 = upWizardNumOfCurKey(blood_a_ , blood_b_ - wizard_x, wizard_num +1, dp);
        int choice2 = dp.get(key2);

        // 当次选择3: 对a和b怪物使用一次y技能
        String key3 = upWizardNumOfCurKey(blood_a_ - wizard_y, blood_b_- wizard_y, wizard_num +1, dp);
        int choice3 = dp.get(key3);
        return getMinimunNum(getMinimunNum(choice1,choice2), choice3);
    }


    private static String getDpKey(int blood_a_, int blood_b_){
        return blood_a_ + "&" + blood_b_;
    }

    /**
     * 生成动态规划Hash表的key
     * 并且更新动态规划的Hash表的value值
     * @param blood_a_
     * @param blood_b_
     * @param wizard_num
     * @param dp
     * @return 动态规划Hash表的当前key
     */
    private static String upWizardNumOfCurKey(int blood_a_, int blood_b_, Integer wizard_num, HashMap<String, Integer> dp){
        String key = getDpKey(blood_a_, blood_b_);

        dp.put(key, wizard_num);
//        dp.putIfAbsent(key, wizard_num);
//        dp.computeIfPresent(key, (k,v) -> v = Math.min(dp.get(key), wizard_num));

//        dp.merge(key, wizard_num, (k,v) -> v = Math.min(dp.get(key), wizard_num));
        return key;
    }

    /**
     * 这个是使用claude3.5 优化出来的
     * 使用动态规划实现击杀怪物所需的最少法术次数
     * @param blood_a 怪物A的血量
     * @param blood_b 怪物B的血量
     * @param wizard_x 小红单体技能x的血量伤害
     * @param wizard_y 小红群体技能y的血量伤害
     * @return 使用最少法术击杀a和b怪物的次数
     */
    private static int getUsedWizardTimesWithDP(int blood_a, int blood_b, double wizard_x, double wizard_y) {

        // dp[i][j] 表示怪物A剩余i血量，怪物B剩余j血量时所需的最少法术次数
        int[][] dp = new int[blood_a + 1][blood_b + 1];

        // 初始化边界条件
        for (int i = 0; i <= blood_a; i++) {
            for (int j = 0; j <= blood_b; j++) {
                if (i <= 0 && j <= 0) {
                    dp[i][j] = 0;
                } else if (i <= 0) {
                    // 只需要击杀怪物B
                    dp[i][j] = (int) Math.ceil(j / Math.max(wizard_x, wizard_y));
                } else if (j <= 0) {
                    // 只需要击杀怪物A
                    dp[i][j] = (int) Math.ceil(i / Math.max(wizard_x, wizard_y));
                } else if (i <= wizard_y && j <= wizard_y) {
                    // 一个群体技能可以同时击杀两个怪物
                    dp[i][j] = 1;
                } else {
                    // 初始化为最大值
                    dp[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        // 动态规划填表
        for (int i = 1; i <= blood_a; i++) {
            for (int j = 1; j <= blood_b; j++) {
                if (i <= wizard_y && j <= wizard_y) {
                    continue; // 已经初始化为1
                }

                // 选择1：对怪物A使用单体技能
                int choice1 = dp[Math.max(0, (int)(i - wizard_x))][j] + 1;

                // 选择2：对怪物B使用单体技能
                int choice2 = dp[i][Math.max(0, (int)(j - wizard_x))] + 1;

                // 选择3：使用群体技能
                int choice3 = dp[Math.max(0, (int)(i - wizard_y))][Math.max(0, (int)(j - wizard_y))] + 1;

                // 取三种选择中的最小值
                dp[i][j] = Math.min(Math.min(choice1, choice2), choice3);
            }
        }

        return dp[blood_a][blood_b];
    }

    /**
     *
     * @param blood_a 怪物A的血量
     * @param blood_b 怪物B的血量
     * @param wizard_x 小红单体技能x的血量伤害
     * @param wizard_y 小红群体技能y的血量伤害
     * @return
     */
    private static int getUsedWizardTimes(int blood_a, int blood_b, int wizard_x, int wizard_y) {

        MonsterStatus monsterStatus = new MonsterStatus(blood_a,blood_b);

        while (!monsterStatus.isKilled) {
            useWizard(monsterStatus, wizard_x , wizard_y);
        }

        monsterStatus.wizard_name.forEach(e -> {
            System.out.println(e);
        });

        return monsterStatus.wizard_num;
    }

    /**
     * 迭代的具体算法
     * @return 本次使用招数的结果
     */
    private static MonsterStatus useWizard(MonsterStatus monsterStatus, int x_harm_value, int y_harm_value ) {

        // 如果a 和 b 血量都小于等于0，怪物就完成击杀
        if (monsterStatus.blood_a_ <= 0 && monsterStatus.blood_b_ <= 0) {
            monsterStatus.wizard_name.add("怪物已经被击杀");
            monsterStatus.isKilled = true;
            return monsterStatus;
        }

        // 下面的逻辑，一定会触发 释放技能

        // 使用招数次数 + 1
        monsterStatus.wizard_num ++;


        //如果y技能对单个怪物的 血量伤害 大于等于x技能
        if (x_harm_value <= y_harm_value ) {
            monsterStatus.blood_a_ -= y_harm_value;
            monsterStatus.blood_b_ -= y_harm_value;
            monsterStatus.wizard_name.add("小红使用一次Y技能");
            return monsterStatus;
        }


        // 下面的是 y技能对单个怪物的 血量伤害 小于 x技能, 单总伤害量大于 x
        if (y_harm_value * 2 >= x_harm_value &&  x_harm_value > y_harm_value ) {

            if (monsterStatus.blood_a_ <= 0) {
                monsterStatus.blood_b_ -= x_harm_value;
                monsterStatus.wizard_name.add("小红对怪物b使用一次x技能");
                return monsterStatus;
            }else if (monsterStatus.blood_b_ <= 0) {
                monsterStatus.blood_a_ -= x_harm_value;
                monsterStatus.wizard_name.add("小红对怪物a使用一次x技能");
                return monsterStatus;
            } else {
                monsterStatus.blood_a_ -= y_harm_value;
                monsterStatus.blood_b_ -= y_harm_value;
                monsterStatus.wizard_name.add("小红使用一次Y技能");
                return monsterStatus;
            }
        }


        // x技能的伤害 比 y技能的伤害总量大
        if (x_harm_value > y_harm_value * 2 ) {

            if (monsterStatus.blood_a_ <= 0 ) {
                monsterStatus.blood_b_ -= x_harm_value;
                monsterStatus.wizard_name.add("小红对怪物b使用一次x技能");
                return monsterStatus;
            }

            if (monsterStatus.blood_b_ <= 0) {
                monsterStatus.blood_a_ -= x_harm_value;
                monsterStatus.wizard_name.add("小红对怪物a使用一次x技能");
                return monsterStatus;
            }

            if ( monsterStatus.blood_a_ <= y_harm_value ) {
                monsterStatus.blood_a_ -= y_harm_value;
                monsterStatus.blood_b_ -= y_harm_value;
                monsterStatus.wizard_name.add("小红使用一次Y技能");
                return monsterStatus;
            }

            if (monsterStatus.blood_b_ <= y_harm_value ) {
                monsterStatus.blood_a_ -= y_harm_value;
                monsterStatus.blood_b_ -= y_harm_value;
                monsterStatus.wizard_name.add("小红使用一次Y技能");
                return monsterStatus;
            }

            if ( monsterStatus.blood_a_ > y_harm_value ) {
                monsterStatus.blood_a_ -= x_harm_value;
                monsterStatus.wizard_name.add("小红对怪物a使用一次x技能");
                return monsterStatus;
            }

            if (monsterStatus.blood_b_ > y_harm_value ) {
                monsterStatus.blood_b_ -= x_harm_value;
                monsterStatus.wizard_name.add("小红对怪物b使用一次x技能");
                return monsterStatus;
            }
        }

        return monsterStatus;
    }



    private static int getMinimunNum(int num_a, int num_b){
        return Math.min(num_a, num_b);
    }

    /**
     * 每次使用招数后，怪物剩余的血量
     * 本次招数使用的是哪一找
     */
    static class MonsterStatus {
        // 怪物a在一次招数后 剩余的血量
        int blood_a_;

        // 怪物b在一次招数后 剩余的血量
        int blood_b_;

        // 本次出招使用的招数名称
        List<String> wizard_name = new ArrayList<>();

        // 使用招数次数
        int wizard_num;

        // 是否被击杀来
        boolean isKilled;

        public MonsterStatus(int blood_a_, int blood_b_) {
            this.blood_a_ = blood_a_;
            this.blood_b_ = blood_b_;
        }
    }
}
